Segmentation and reassembly (SAR) of units of data (such as packets or cells) that are transferred between elements (also called “store and forward elements”) of a communication network is performed to break up large data units into smaller, more manageably sized data units. The need to break up a data unit may arise, for example, if the data unit is of a length greater than a maximum length permitted by a portion of the network. Once broken up, such fragments of a data unit are sequentially transmitted, may traverse different network paths, and must be reassembled at a destination.
For example, when performing voice trunking over ATM (asynchronous transfer mode) using AAL2 for narrowband services (e.g. as described in ATM Forum standard AF-VTOA-0113.000), a number of packets (called CPS packets) are generated and embedded in ATM cells that are transmitted to a remote device. CPS stands for “common part sublayer”. At the destination, a number of ATM cells are processed by a SAR device 101 (FIG. 1A) to recover the CPS packets. SAR device 101 may use an external memory to temporarily hold data during such processing. Depending on the application, several CPS packets may be received, as payload in an ATM cell. In some cases, only a portion of a CPS packet is present at the end of the cell, with the remainder of the packet being at the beginning of the next cell.
A network processor 102 and a switch fabric 103 normally process each CPS packet retrieved by the SAR device. For example, network processor 102 may perform classification, metering and/or ATM policing of the CPS packets, collect statistics, and perform operation and maintenance (OAM) functions. Switch fabric 103 (and/or a traffic manager) provides a number of fixed size buffers for temporary storage, and also performs per-flow queuing and scheduling, implements dynamic discard thresholds and random early detection. Switch fabric 103 (and/or a traffic manager) is typically connected to other network processors either directly or via an interconnect fabric (not shown).
Instead of performing segmentation and reassembly (SAR) in hardware, these functions can be implemented in software that is programmed into network processor 106 (FIG. 1B). In such a case, network processor 106 may use a doubly linked list implemented in a memory 105 to temporarily hold the data. For example, if an incoming unit of data is a fragment of a packet in conformance with the Internet Protocol (IP), network processor 102 may attempt to match its source and destination addresses to an existing entry in such a linked list. If there is a match, network processor 106 may check if the complete datagram has arrived and if not, add the fragment to the linked list for use in future when the last fragment has arrived. Otherwise, if the complete datagram has arrived, network processor 106 may assemble the datagram in sequence and then transmit the datagram to a queue in switch fabric 103 (also called egress queue).
Instead of using a doubly linked list, a software implementation in network processor 106 may use a number of queues also implemented in memory 105, with each queue being limited to holding multiple fragments of a single datagram. Note that in FIGS. 1A and 1B, the network processors may be identical although different reference numbers 102 and 106 have been used to indicate that these network processors are programmed differently.
Network processors (also called communications processors) of the type described above may perform one or more of the following functions (called “network processing functions”): parsing, searching, resolving and modifying. During parsing, a network processor analyzes and classifies the contents of the header and fields. During searching, tables are searched for a match between the content that was classified and pre-defined content and rules. During resolving, the destination and quality of service (QoS) requirements are resolved and the packet/cell is routed to its destination. During modifying, where necessary, the packet/cell is modified, e.g. certain fields (such as time to live and checksum) within the packet/cell are changed. Examples of commercially available network processors include: Intel's IXP1200, Agere's Payload Plus, AMCC's nP7250, IBM's PowerNP NP4GS3, Motorola's C-Port C-5 and Vitesse's IQ2000.
A network processor of the type described above is typically coupled to and used with a traffic manager and/or a switch fabric. Either or both devices (traffic manager and/or switch fabric) may perform one or more of the following functions: queuing and output scheduling (round robin, weighted fair queuing), policing of traffic flows to assure quality of service, traffic shaping (e.g. to meet delay or jitter requirements), statistics collection, congestion management and provisioning. Examples of commercially available devices that perform switch fabric functions include: Motorola's Q5 TMC, and AMCC's nPX5710/nPX5720 (together referred to as nPX5700).
For traffic management as well as for switching, each packet/cell must be stored in memory and later transmitted. The above-described functions may be implemented together in a chipset consisting of two chips: a traffic manager (such as AMCC's nPX5710) and a memory manager (such as AMCC's nPX5720). The just-described two chips are normally used together and frequently treated as a single device that contains queues. Such a queue-containing device may have four ports, each of which is coupled to a network processor by serial links operating at 2.5 Gbps or 10 Gbps.
Buffering of traffic is typically implemented via an external memory attached to the memory manager. Typical requirements in today's networks may require traffic up to two hundred and fifty six thousand (256K) queues to be managed. In some implementations, at any given time, only information related to a subset of these queues (e.g. up to eight thousand queues) may be cached on chip (e.g. in DDR SDRAM or RDRAM) by taking advantage of statistical multiplexing (i.e. the likelihood that the incoming traffic belongs to more than eight thousand queues is very low). Therefore, eight thousand queues (containing packets/cells) are stored in a buffering chip (such as AMCC's nPX5720) having embedded DRAM channels for example, and these queues are managed by a control logic chip (such as AMCC's nPX5710). These two chips when used together act as a switch fabric and traffic manager.
Incorporated by reference herein in their entirety are the following references:
U.S. Pat. No. 6,307,860 granted to Joffe, et al. on Oct. 23, 2001, and entitled “Systems and methods for data transformation and transfer in networks”;
U.S. Pat. No. 6,330,584 granted to Joffe, et al. on Dec. 11, 2001, and entitled “Systems and methods for multi-tasking, resource sharing and execution of computer instructions”;
U.S. Pat. No. 5,901,147 granted to Joffe on May 4, 1999, and entitled “Apparatus and methods to change thresholds to control congestion in ATM switches”; and
U.S. Pat. No. 6,128,278 granted to Joffe, et al. on Oct. 3, 2000 and entitled “Cell queuing in ATM switches.”